package Queue;

import java.util.LinkedList;
import java.util.Queue;

/**
 *  题目 ：最近请求次数
 *  题目详述 ：
 *
 *  写一个RecentCounter类来计算特定时间范围内最近的请求。
 *  请你实现 RecentCounter 类：
 *  RecentCounter() 初始化计数器，请求数为 0 。
 *  int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。
 *  确切地说，返回在 [t-3000, t] 内发生的请求数。
 *  保证 每次对 ping 的调用都使用比之前更大的 t 值。
 */
public class RecentCounter {
    /**
     *  核心思想 ：
     *  由于是通过ping方法，来统计请求次数，即统计区间在[t - 3000 , t]；
     *  类似于滑动窗口，即若是之前那个请求所保存的值，已经小于t - 3000时，需要将其从队列中删除；
     *  即，只需要去统计队列大小，即可获取区间内的请求数；
     */
    Queue<Integer> queue; // 定义队列，来存储请求
    Integer size;
    public RecentCounter() {
        // 初始化操作，都在构造函数中进行操作；
        queue = new LinkedList<>(); // 初始化队列；
        size = 3000; // 定义区间大小；
    }

    public int ping(int t) {
        // 1.任何元素都需要先插入队列
        queue.offer(t);// queue.offer()方法，不会报异常；
        while (t > queue.peek() + size){
            // 即，当所插入的请求 > 队列的首个请求 + 区间
            // 使用while循环，直到队列的首个请求在范围区间内
            queue.poll();
        }
        return queue.size();
    }
    /**
     *  分析 ：
     *  （1）空间复杂度 ：根据队列的大小决定，即存在于队列中的请求数w
     *   ===》 O（w）；
     *   (2)时间复杂度 ：O（1）；
     */
}
